#include <iostream>

// AST节点定义
class Expr {
public:
    virtual ~Expr() = default;
    virtual int eval() const = 0;
};

class IntegerExpr : public Expr {
public:
    IntegerExpr(int val) : value(val) {}
    int eval() const override { return value; }
private:
    int value;
};

class BinaryExpr : public Expr {
public:
    BinaryExpr(Expr* l, Expr* r, char op) : left(l), right(r), op(op) {}
    ~BinaryExpr() override {
        delete left;
        delete right;
    }
    int eval() const override {
        int l = left->eval();
        int r = right->eval();
        switch(op) {
            case '+': return l + r;
            case '-': return l - r;
            case '*': return l * r;
            case '/': return l / r;
        }
        return 0;
    }
private:
    Expr* left;
    Expr* right;
    char op;
};

// 常量折叠优化的函数
Expr* fold_constants(Expr* expr) {
    if (auto* int_expr = dynamic_cast<IntegerExpr*>(expr)) {
        // 整数表达式
        return new IntegerExpr(int_expr->eval());
    } else if (auto* binary_expr = dynamic_cast<BinaryExpr*>(expr)) {
        // 二元运算表达式
        Expr* l = fold_constants(binary_expr->left);
        Expr* r = fold_constants(binary_expr->right);
        if (auto* l_int = dynamic_cast<IntegerExpr*>(l)) {
            if (auto* r_int = dynamic_cast<IntegerExpr*>(r)) {
                // 两个操作数都是整数，可以进行常量折叠
                return new IntegerExpr(BinaryExpr(l_int, r_int, binary_expr->op).eval());
            }
        }
        // 无法进行常量折叠，返回原始的表达式
        return new BinaryExpr(l, r, binary_expr->op);
    } else {
        // 不是整数表达式或二元运算表达式，返回原始的表达式
        return expr;
    }
}

// 用例
int main() {
    Expr* expr = new BinaryExpr(new IntegerExpr(1), new BinaryExpr(new IntegerExpr(2), new IntegerExpr(3), '*'), '+');
    expr = fold_constants(expr);
    std::cout << expr->eval() << std::endl; // 输出 7
    delete expr;
    return 0;
}

//这段代码演示了一个简单的AST，由两种节点组成：IntegerExpr表示整数表达式，
// BinaryExpr表示二元运算表达式。fold_constants函数实现了一个简单的常量折叠优化，
// 它递归地遍历AST节点，对于整数表达式直接求值，对于二元运算表达式，如果它的两个操作数都是整数表达式，则进行常量折叠，返回一个新的整数表达式节点，
// 否则返回原始的二元运算表达式节点。在用例中，我们构造了一个简单的AST，然后对它进行常量折叠，输出结果为7。
